import java.util.ArrayList;
import java.util.List;

class Solution {
    List<String> ret = new ArrayList<>();
    public void backTracing(String s,int startIndex,int pointNum){
        //终止条件
        if(pointNum==3){
            //如果小数点为3个时,第四个字符必须是有效字符
            if(isValid(s,startIndex,s.length()-1)){
                ret.add(s);
                return ;
            }
        }
        for(int i = startIndex;i<s.length();++i){
            //必须要在该字符串合法的情况下
            if(isVaild(s,startIndex,i)){
               //将字符串加上小数点
               s = s.substring(0,i+1) + "." + s.substring(i+1);
               pointNum++;
               //要跳过小数点
               backTracing(s,i+2,pointNum);
               //去掉小数点
               s = s.substring(0,i+1) + s.substring(i+2);
               pointNum--;
            }else {
                break;
            }
        }
    }

    private Boolean isValid(String s, int start, int end) {
        if (start > end) {
            return false;
        }
        if (s.charAt(start) == '0' && start != end) { // 0开头的数字不合法
            return false;
        }
        int num = 0;
        for (int i = start; i <= end; i++) {
            if (s.charAt(i) > '9' || s.charAt(i) < '0') { // 遇到⾮数字字符不合法
                return false;
            }
            num = num * 10 + (s.charAt(i) - '0');
            if (num > 255) { // 如果⼤于255了不合法
                return false;
            }
        }
        return true;
    }
    public boolean isVaild(String s,int start,int end){
        if(start>end) return false;//字符串不合法
        char[] str = s.toCharArray();
        //如果是前导0字符串,那证明不合法
        if(str[start]=='0'&&start==end) return false;
        int num = 0;
        for(int i = start;i<=end;++i){
            if(str[i]<'0'||str[i]>'9'){
                return false;
            }
            num = num*10+str[i];
            if(num>255){
                return false;
            }
        }
        return true;
    }

    public List<String> restoreIpAddresses(String s) {
        if(s.length()<4||s.length()>12) return ret;
        backTracing(s,0,0);
        return ret;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        solution.restoreIpAddresses("25525511135");
    }


}